#include <stdio.h>
#include "common.h"

/* 堆 数据结构实现 */

typedef struct
{
    int *array;
    int n;
} heap;

void buildHeap(int array[], int n);
void heapify(int array[], int n, int i);

void main()
{
    int array[] = {-1, 7, 5, 19, 8, 4, 1, 20, 13, 16};
    int len = 10;
    buildHeap(array, len - 1);
    print(array, len);
}

void buildHeap(int array[], int n)
{
    for (int i = n / 2; i >= 1; i--)
    {
        heapify(array, n, i);
    }
}

void heapify(int array[], int n, int i)
{
    while (1)
    {
        int maxPos = i;
        int leftPos = i * 2;
        int rightPos = i * 2 + 1;
        if (leftPos <= n && array[maxPos] < array[leftPos])
        {
            maxPos = leftPos;
        }
        if (rightPos <= n && array[maxPos] < array[rightPos])
        {
            maxPos = rightPos;
        }

        if (maxPos == i)
            break;

        int temp = array[i];
        array[i] = array[maxPos];
        array[maxPos] = temp;
        i = maxPos;
    }
}
